import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Text {
    //给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
    // s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
    public List<Integer> findSubstring(String s, String[] words) {
        //先定义一个顺序表来接受一下返回的数据
        List<Integer> list = new ArrayList<>();
        //创建一个哈希表保存数据
        Map<String,Integer> hash1 = new HashMap<>();
        for (String str : words ) {
            //加入哈希表
            hash1.put(str,hash1.getOrDefault(str,0)+ 1);
        }
        int n = words.length; //单词的个数
        int len = words[0].length();  //一个单词的长度

        //执行的次数  取决于 一个单词的长度
        for (int i = 0; i < len; i++) {
            Map<String,Integer> hash2 = new HashMap<>();  //保存窗口内单词出现的频率
            for(int left = i,right = i,count = 0;right + len <= s.length();right+=len) {
                //进窗口
                String in = s.substring(right,right+len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if (hash2.get(in) <= hash1.getOrDefault(in,0)) {
                    count++;
                }
                //判断  出窗口
                if ((right - left + 1) > n * len) {
                    String out = s.substring(left,left+len);
                    //维护count
                    if (hash2.get(out) <= hash1.getOrDefault(out,0)) {
                        count--;  //删掉的是有效数据 所以count--
                    }
                    //把单词移出哈希表
                    hash2.put(out,hash2.getOrDefault(out,0) - 1);
                    left += len; // left继续右移

                }
                //更新结果
                if (count == n) {
                    list.add(left);
                }

            }
        }
        return list;
    }
    //找出字符串中所有字母的异位词
    //给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
    //异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

    public List<Integer> findAnagrams(String ss, String pp) {
        //创建一个顺序表来存储数据
        List<Integer> list = new ArrayList<>();
        //先分别把两个字符串转化为字符
        char[] p = pp.toCharArray();
        char[] s = ss.toCharArray();
        //创建一个哈希表来存pp的字符
        int[] hash1 = new int[26];  //26个字母
        for(char ch : p){
            hash1[ch - 'a'] ++;
        }
        //再定义一个哈希表来存 ss的字符
        int[] hash2 = new int[26];
        int m = pp.length();  //记录一下 字符串pp的长度
        int n = ss.length();
        for(int left = 0,right = 0,count = 0;right < n; right++) {
            char in = s[right];
            //进窗口 +维护count
            if(++hash2[in-'a'] <= hash1[in - 'a']) count++;  //就是说如果表2的里面的个数小于表1的 说明是有效个数
            //判断
            if(right - left + 1 > m ) {
                //说明left要++了
                char out = s[left++];
                //出窗口  //继续维护count
                if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            //保存索引
            if(count == m) list.add(left);

        }
        return list;
    }

    //水果成篮   就是找出最长的子数组  子数组的水果种类不能超过2
    public int totalFruit(int[] fruits) {
        //先求出数组的长度   并用数组来模拟哈续表
        int n = fruits.length;
        int[] hash = new int[n+1];
        //记录一下长度
        int ret = 0;
        for(int left = 0,right = 0,count = 0; right < n;right++) {
            int start = fruits[right];
            if(hash[start] == 0) {
                count++;  //只要是新的种类水果进来  count就++
            }
            hash[start]++;
            while(count > 2) {
                int out = fruits[left];
                hash[out]--;
                //如果出窗口后 水果种类在哈希表中为0  说明 水果种类就要减减
                if(hash[out] == 0) {
                    count--;
                }
                left++;
            }
            ret = Math.max(ret,right - left + 1);
        }
        return ret;
    }
    public static void main(String[] args) {

    }
}
